package com.cqs.leetcode.string.sliding.windws;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lixiaowen
 * @create 2019-12-17
 */
public class LongestSubstringWithoutRepeatingCharacters3 {


public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) return 0;
    char[] chars = s.toCharArray();
    int max = 0, left = 0, right = -1;
    //窗口中包含的字符
    int[] contains = new int[256];
    while (right < s.length()){
        //right 右移，直至找到局部为最大不重复子串
        while ((right + 1 < chars.length) && contains[chars[right+1]] == 0 ){
            contains[chars[++right]] = 1;
        }
        max = Math.max(right - left + 1, max);
        //寻找下一个窗口
        ++right;
        if (right == s.length()) break;
        //移动left直到窗口字符均不重复
        while (left < right && chars[left] != chars[right]){
            contains[chars[left++]] = 0;
        }
        ++left;
    }
    return max;
}

    public static void main(String[] args) {
        LongestSubstringWithoutRepeatingCharacters3 lg = new LongestSubstringWithoutRepeatingCharacters3();
        List<String> testCase = new ArrayList<>();
        testCase.add("");
        testCase.add("aa");
        testCase.add("aaaaa");
        testCase.add("abababab");
        testCase.add("abcacbbsdd");
        testCase.add("pwwkew");
        testCase.forEach(s -> {
            System.out.println(s+ "=> "+lg.lengthOfLongestSubstring(s));
        });
    }
}
